package test.n00400;


import java.util.ArrayList;
import java.util.List;

import static utils.Tools.listOf;

public class Problem00461 {
    public static void main(String[] args) {
        println(new int[]{1, 2, 3});
    }

    public static void println(int[] nums) {
        Solution ss = new Solution();
        System.out.println(listOf(nums) + "," + ss.permute(nums));
    }

    public static class Solution {

        /**
         * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
         * <p>
         * 解题思路:
         * 回溯+深度优先搜索(dfs)
         *
         * @param nums
         * @return
         */
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            int len = nums.length;
            if (len == 0) {
                return result;
            }

            boolean[] used = new boolean[len];
            dfs(nums, len, 0, new ArrayList<>(), used, result);
            return result;
        }

        public void dfs(
                int[] nums,
                int len,
                int depth,
                List<Integer> path,
                boolean[] used,
                List<List<Integer>> result
        ) {

            if (depth == len) {
                result.add(new ArrayList<>(path));
                return;
            }

            for (int i = 0; i < len; i++) {
                if (used[i]) {
                    continue;
                }

                path.add(nums[i]);
                used[i] = true;

                dfs(nums, len, depth + 1, path, used, result);

                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
}
